import numpy as np

def pca(X,k):#k is the components you want
  #mean of each feature
  n_samples, n_features = X.shape
  mean=np.array([np.mean(X[:,i]) for i in range(n_features)])
  #normalization
  norm_X=X-mean
  #scatter matrix
  scatter_matrix=np.dot(np.transpose(norm_X),norm_X)
  #Calculate the eigenvectors and eigenvalues
  eig_val, eig_vec = np.linalg.eig(scatter_matrix)
  eig_pairs = [(np.abs(eig_val[i]), eig_vec[:,i]) for i in range(n_features)]
  # sort eig_vec based on eig_val from highest to lowest
  eig_pairs.sort(reverse=True)
  # select the top k eig_vec
  feature=np.array([ele[1] for ele in eig_pairs[:k]])
  #get new data
  data=np.dot(norm_X,np.transpose(feature))
  return data

def lda(data, target, n_dim):
    '''
    :param data: (n_samples, n_features)
    :param target: data class
    :param n_dim: target dimension
    :return: (n_samples, n_dims)
    '''

    clusters = np.unique(target)

    if n_dim > len(clusters) - 1:
      print("K is too much")
      print("please input again")
      exit(0)

    # within_class scatter matrix
    Sw = np.zeros((data.shape[1], data.shape[1]))
    for i in clusters:
      datai = data[target == i]
      datai = datai - datai.mean(0)
      Swi = np.mat(datai).T * np.mat(datai)
      Sw += Swi

    # between_class scatter matrix
    SB = np.zeros((data.shape[1], data.shape[1]))
    u = data.mean(0)  # 所有样本的平均值
    for i in clusters:
      Ni = data[target == i].shape[0]
      ui = data[target == i].mean(0)  # 某个类别的平均值
      SBi = Ni * np.mat(ui - u).T * np.mat(ui - u)
      SB += SBi
    S = np.linalg.inv(Sw) * SB
    eigVals, eigVects = np.linalg.eig(S)  # 求特征值，特征向量
    eigValInd = np.argsort(eigVals)
    eigValInd = eigValInd[:(-n_dim - 1):-1]
    w = eigVects[:, eigValInd]
    data_ndim = np.dot(data, w)

    return data_ndim

